//Given n non-negative integers representing an elevation map where the width of
// each bar is 1, compute how much water it can trap after raining. 
//
// 
// Example 1: 
//
// 
//Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
//Output: 6
//Explanation: The above elevation map (black section) is represented by array [
//0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are
// being trapped.
// 
//
// Example 2: 
//
// 
//Input: height = [4,2,0,3,2,5]
//Output: 9
// 
//
// 
// Constraints: 
//
// 
// n == height.length 
// 0 <= n <= 3 * 104 
// 0 <= height[i] <= 105 
// 
// Related Topics 栈 数组 双指针 动态规划 
// 👍 2300 👎 0


package leetcode.editor.cn;

import org.junit.Assert;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

//Java：Trapping Rain Water
class P42TrappingRainWater {
    public static void main(String[] args) {
        Solution solution = new P42TrappingRainWater().new Solution();
        // TO TEST
        //9
        Assert.assertEquals(solution.trapStack(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}), 6);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int trapStack(int[] height) {
            int ans = 0;
            Deque<Integer> stack = new LinkedList<Integer>();
            int n = height.length;
            for (int i = 0; i < n; ++i) {
                while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                    int top = stack.pop();
                    if (stack.isEmpty()) {
                        break;
                    }
                    int left = stack.peek();
                    int currWidth = i - left - 1;
                    int currHeight = Math.min(height[left], height[i]) - height[top];
                    ans += currWidth * currHeight;
                }
                stack.push(i);
            }
            return ans;
        }


        public int traping(int[] height) {
            int sum = 0;
            if (height == null || height.length == 0 || height.length == 1 || height.length == 2) {
                return sum;
            }
            int len = height.length;
            int[] leftMax = new int[len];
            int[] rightMax = new int[len];
            leftMax[0] = height[0];
            rightMax[len - 1] = height[len - 1];
            for (int i = 1; i < len; i++) {
                leftMax[i] = Math.max(height[i], leftMax[i - 1]);
            }
            for (int i = len - 2; i >= 0; i--) {
                rightMax[i] = Math.max(height[i], rightMax[i + 1]);
            }
            for (int i = 1; i < len - 1; i++) {
                sum += Math.min(leftMax[i], rightMax[i]) - height[i];
            }
            return sum;
        }

        //1.遍历一次
        public int trappingWater(int[] height) {
            int left = 0, right = height.length - 1;
            int leftWall = height[0], rightWall = height[height.length - 1];
            int sum = 0;
            while (left < right) {
                if (height[right] > height[left]) {
                    if (leftWall > height[left]) {
                        sum += Math.min(height[right], leftWall) - height[left];
                    } else {
                        leftWall = height[left];
                    }
                    left++;
                } else {
                    if (rightWall > height[right]) {
                        sum += Math.min(height[left], rightWall) - height[right];
                    } else {
                        rightWall = height[right];
                    }
                    right--;
                }
            }
            return sum;
        }

        public int trap(int[] height) {
            int sum = 0;
            int[] leftWall = Arrays.copyOfRange(height, 0, height.length);
            int[] rightWall = Arrays.copyOfRange(height, 0, height.length);
            for (int i = 1; i < height.length; i++) {
                if (leftWall[i - 1] > height[i]) {
                    leftWall[i] = leftWall[i - 1];
                }
            }
            for (int i = height.length - 2; i >= 0; i--) {
                if (rightWall[i + 1] > height[i]) {
                    rightWall[i] = rightWall[i + 1];
                }
            }
            for (int i = 0; i < rightWall.length; i++) {
                sum += Math.min(leftWall[i], rightWall[i]) - height[i];
            }
            return sum;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}